SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Zero-knowledge proof</title>

</head>

Zero-knowledge proof

</h1>

</header>

In <a href="Cryptography" title="Cryptography">cryptography</a>, a zero-knowledge proof (also known as a ZK proof or ZKP) is a protocol in which one party (the prover) can convince another party (the verifier) that some given statement is true, without conveying to the verifier any information beyond the mere fact of that statement's truth.<a href="#cite_note-1">[1]</a> The intuition underlying zero-knowledge proofs is that it is trivial to prove possession of the relevant information simply by revealing it; the hard part is to prove this possession without revealing this information (or any aspect of it whatsoever).<a href="#cite_note-2">[2]</a>

In light of the fact that one should be able to generate a proof of some statement only when in possession of certain secret information connected to the statement, the verifier, even after having become convinced of the statement's truth, should nonetheless remain unable to prove the statement to further third parties.

Zero-knowledge proofs can be interactive, meaning that the prover and verifier exchange messages according to some protocol, or noninteractive, meaning that the verifier is convinced by a single prover message and no other communication is needed. In the <a href="Standard_model_(cryptography)" title="Standard model (cryptography)">standard model</a>, interaction is required, except for trivial proofs of <a href="BPP_(complexity)" title="BPP (complexity)">BPP</a> problems.<a href="#cite_note-3">[3]</a> In the common random string and <a href="Random_oracle" title="Random oracle">random oracle</a> models, <a href="Non-interactive_zero-knowledge_proof" title="Non-interactive zero-knowledge proof">non-interactive zero-knowledge proofs</a> exist. The <a href="Fiat%E2%80%93Shamir_heuristic" title="Fiat–Shamir heuristic">Fiat–Shamir heuristic</a> can be used to transform certain interactive zero-knowledge proofs into noninteractive ones.<a href="#cite_note-4">[4]</a><a href="#cite_note-noninteractive-5">[5]</a><a href="#cite_note-noninteractive2-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Abstract_examples">Abstract examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="The_red_card_proof">The red card proof</h3></div>

One example of a math-free zero knowledge proof is if Peggy wants to prove to Victor that she has drawn a red card from a standard deck of 52 playing cards, without revealing which specific red card she holds. Victor observes Peggy draw a card at random from the shuffled deck, but she keeps the card face-down so he cannot see it.

To prove her card is red without revealing its identity, Peggy takes the remaining 51 cards from the deck and systematically shows Victor all 26 black cards (the 13 spades and 13 clubs) one by one, placing them face-up on the table. Since a standard deck contains exactly 26 red cards and 26 black cards, and Peggy has demonstrated that all the black cards remain in the deck, Victor can conclude with certainty that Peggy's hidden card must be red.

This proof is zero-knowledge because Victor learns only that Peggy's card is red, but gains no information about whether it is a heart or diamond, or which specific red card she holds. The proof would be equally convincing whether Peggy held the Ace of Hearts or the Two of Diamonds. Furthermore, even if the interaction were recorded, the recording would not reveal Peggy's specific card to future observers, maintaining the zero-knowledge property.

If Peggy was lying and actually held a black card, she would be unable to produce all 26 black cards from the remaining deck, making deception impossible. This demonstrates the soundness of the proof system. This type of physical zero-knowledge proof using standard playing cards belongs to a broader class of card-based cryptographic protocols that allow participants to perform secure computations using everyday objects.<a href="#cite_note-7">[7]</a>

<div class="mw-heading mw-heading3"><h3 id="Where's_Wally">Where's Wally</h3></div>

Another well-known example of a zero-knowledge proof is the "Where's Wally" example. In this example, the prover wants to prove to the verifier that they know where Wally is on a page in a <a href="Where's_Wally%3F" title="Where's Wally?">Where's Wally?</a> book, without revealing his location to the verifier.<a href="#cite_note-Murtagh-8">[8]</a>

The prover starts by taking a large black board with a small hole in it, the size of Wally. The board is twice the size of the book in both directions, so the verifier cannot see where on the page the prover is placing it. The prover then places the board over the page so that Wally is in the hole.<a href="#cite_note-Murtagh-8">[8]</a>

The verifier can now look through the hole and see Wally, but cannot see any other part of the page. Therefore, the prover has proven to the verifier that they know where Wally is, without revealing any other information about his location.<a href="#cite_note-Murtagh-8">[8]</a>

This example is not a perfect zero-knowledge proof, because the prover does reveal some information about Wally's location, such as his body position. However, it is a decent illustration of the basic concept of a zero-knowledge proof.

/* start https://en.wikipedia.org/ */

.mw-parser-output .tmulti .multiimageinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;text-align:center}.mw-parser-output .tmulti .tsingle .thumbcaption{text-align:left}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:154px;max-width:154px"><div class="trow"><div class="tsingle" style="width:152px;max-width:152px"><div class="thumbimage"></div><div class="thumbcaption">Peggy randomly takes either path A or B, while Victor waits outside.</div></div></div><div class="trow"><div class="tsingle" style="width:152px;max-width:152px"><div class="thumbimage"></div><div class="thumbcaption">Victor chooses an exit path.</div></div></div><div class="trow"><div class="tsingle" style="width:152px;max-width:152px"><div class="thumbimage"></div><div class="thumbcaption">Peggy reliably appears at the exit Victor names.</div></div></div></div></div>

There is a well-known story presenting the fundamental ideas of zero-knowledge proofs, first published in 1990 by <a href="Jean-Jacques_Quisquater" title="Jean-Jacques Quisquater">Jean-Jacques Quisquater</a> and others in their paper "How to Explain Zero-Knowledge Protocols to Your Children".<a href="#cite_note-9">[9]</a> The two parties in the zero-knowledge proof story are <a href="Alice_and_Bob#Cast_of_characters" title="Alice and Bob">Peggy</a> as the prover of the statement, and <a href="Alice_and_Bob#Cast_of_characters" title="Alice and Bob">Victor</a>, the verifier of the statement.

In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a ring, with the entrance on one side and the magic door blocking the opposite side. Victor wants to know whether Peggy knows the secret word; but Peggy, being a very private person, does not want to reveal her knowledge (the secret word) to Victor or to reveal the fact of her knowledge to the world in general.

They label the left and right paths from the entrance A and B. First, Victor waits outside the cave as Peggy goes in. Peggy takes either path A or B; Victor is not allowed to see which path she takes. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path.

However, suppose she did not know the word. Then, she would only be able to return by the named path if Victor were to give the name of the same path by which she had entered. Since Victor would choose A or B at random, she would have a 50% chance of guessing correctly. If they were to repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor's requests would be reduced to 1 in 220, or 9.54 × 10−7.

Thus, if Peggy repeatedly appears at the exit Victor names, then he can conclude that it is extremely probable that Peggy does, in fact, know the secret word.

One side note with respect to third-party observers: even if Victor is wearing a hidden camera that records the whole transaction, the only thing the camera will record is in one case Victor shouting "A!" and Peggy appearing at A or in the other case Victor shouting "B!" and Peggy appearing at B. A recording of this type would be trivial for any two people to fake (requiring only that Peggy and Victor agree beforehand on the sequence of As and Bs that Victor will shout). Such a recording will certainly never be convincing to anyone but the original participants. In fact, even a person who was present as an observer at the original experiment should be unconvinced, since Victor and Peggy could have orchestrated the whole "experiment" from start to finish.

Further, if Victor chooses his As and Bs by flipping a coin on-camera, this protocol loses its zero-knowledge property; the on-camera coin flip would probably be convincing to any person watching the recording later. Thus, although this does not reveal the secret word to Victor, it does make it possible for Victor to convince the world in general that Peggy has that knowledge—counter to Peggy's stated wishes. However, digital cryptography generally "flips coins" by relying on a <a href="Pseudo-random_number_generator" class="mw-redirect" title="Pseudo-random number generator">pseudo-random number generator</a>, which is akin to a coin with a fixed pattern of heads and tails known only to the coin's owner. If Victor's coin behaved this way, then again it would be possible for Victor and Peggy to have faked the experiment, so using a pseudo-random number generator would not reveal Peggy's knowledge to the world in the same way that using a flipped coin would.

Peggy could prove to Victor that she knows the magic word, without revealing it to him, in a single trial. If both Victor and Peggy go together to the mouth of the cave, Victor can watch Peggy go in through A and come out through B. This would prove with certainty that Peggy knows the magic word, without revealing the magic word to Victor. However, such a proof could be observed by a third party, or recorded by Victor and such a proof would be convincing to anybody. In other words, Peggy could not refute such proof by claiming she colluded with Victor, and she is therefore no longer in control of who is aware of her knowledge.

<div class="mw-heading mw-heading3"><h3 id="Two_balls_and_the_colour-blind_friend">Two balls and the colour-blind friend</h3></div>

Imagine Victor is red-green <a href="Color_blindness" title="Color blindness">colour-blind</a> (while Peggy is not) and Peggy has two balls: one red and one green, but otherwise identical. To Victor, the balls seem completely identical. Victor is skeptical that the balls are actually distinguishable. Peggy wants to prove to Victor that the balls are in fact differently coloured, but nothing else. In particular, Peggy does not want to reveal which ball is the red one and which is the green.

Here is the proof system: Peggy gives the two balls to Victor and he puts them behind his back. Next, he takes one of the balls and brings it out from behind his back and displays it. He then places it behind his back again and then chooses to reveal just one of the two balls, picking one of the two at random with equal probability. He will ask Peggy, "Did I switch the ball?" This whole procedure is then repeated as often as necessary.

By looking at the balls' colours, Peggy can, of course, say with certainty whether or not he switched them. On the other hand, if the balls were the same colour and hence indistinguishable, Peggy's ability to determine whether a switch occurred would be no better than random guessing. Since the probability that Peggy would have randomly succeeded at identifying each switch/non-switch is 50%, the probability of having randomly succeeded at all switch/non-switches approaches zero.

Over multiple trials, the success rate would <a href="Law_of_large_numbers" title="Law of large numbers">statistically converge</a> to 50%, and Peggy could not achieve a performance significantly better than chance. If Peggy and Victor repeat this "proof" multiple times (e.g. 20 times), Victor should become convinced that the balls are indeed differently coloured.

The above proof is zero-knowledge because Victor never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.<a href="#cite_note-10">[10]</a>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

A zero-knowledge proof of some statement must satisfy three properties:

<ol><li>Completeness: if the statement is true, then an honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.</li>

<li>Soundness: if the statement is false, then no cheating prover can convince an honest verifier that it is true, except with some small probability.</li>

<li>Zero-knowledge: if the statement is true, then no verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret. This is formalized by showing that every verifier has some simulator that, given only the statement to be proved (and no access to the prover), can produce a transcript that "looks like" an interaction between an honest prover and the verifier in question.</li></ol>

The first two of these are properties of more general <a href="Interactive_proof_system" title="Interactive proof system">interactive proof systems</a>. The third is what makes the proof zero-knowledge.<a href="#cite_note-11">[11]</a>

Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values (for example, guessing correctly on a hundred or thousand binary decisions has a 1/2100 or 1/21000 soundness error, respectively. As the number of bits increases, the soundness error decreases toward zero).

A formal definition of zero-knowledge must use some computational model, the most common one being that of a <a href="Turing_machine" title="Turing machine">Turing machine</a>. Let P, V, and S be Turing machines. An <a href="Interactive_proof_system" title="Interactive proof system">interactive proof system</a> with (P,V) for a language L is zero-knowledge if for any <a href="Probabilistic_polynomial_time" class="mw-redirect" title="Probabilistic polynomial time">probabilistic polynomial time</a> (PPT) verifier <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {V}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

<msup>

</mrow>

</msup>

<msub>

<mover>

</mover>

</mrow>

</msub>

<mrow>

<mrow>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall x\in L,z\in \{0,1\}^{*},\operatorname {View} _{\hat {V}}\left[P(x)\leftrightarrow {\hat {V}}(x,z)\right]=S(x,z),}</annotation>

</semantics>

</math><img src="./1dc9f4c672b2807b48a34659dc71e6581baceaa9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:54.624ex; height:4.843ex;" alt="{\displaystyle \forall x\in L,z\in \{0,1\}^{*},\operatorname {View} _{\hat {V}}\left[P(x)\leftrightarrow {\hat {V}}(x,z)\right]=S(x,z),}" loading="lazy"></dd></dl>

where View<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {V}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

</math><img src="./82dafc72bc12e1b85747770c7e2d4a48845d4c2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.843ex;" alt="{\displaystyle {\hat {V}}}" loading="lazy">(x,z)] is a record of the interactions between P(x) and V(x,z). The prover P is modeled as having unlimited computation power (in practice, P usually is a <a href="Probabilistic_Turing_machine" title="Probabilistic Turing machine">probabilistic Turing machine</a>). Intuitively, the definition states that an interactive proof system (P,V) is zero-knowledge if for any verifier <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {V}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

</math><img src="./82dafc72bc12e1b85747770c7e2d4a48845d4c2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.843ex;" alt="{\displaystyle {\hat {V}}}" loading="lazy"> cannot use any prior knowledge string z to mine information out of its conversation with P, because if S is also given this prior knowledge then it can reproduce the conversation between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {V}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

The definition given is that of perfect zero-knowledge. Computational zero-knowledge is obtained by requiring that the views of the verifier <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {V}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}}</annotation>

</semantics>

<div class="mw-heading mw-heading2"><h2 id="Practical_examples">Practical examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Discrete_log_of_a_given_value">Discrete log of a given value</h3></div>

These ideas can be applied to a more realistic cryptography application. Peggy wants to prove to Victor that she knows the <a href="Discrete_logarithm" title="Discrete logarithm">discrete logarithm</a> of a given value in a given <a href="Group_theory" title="Group theory">group</a>.<a href="#cite_note-12">[12]</a>

For example, given a value y, a large <a href="Prime_number" title="Prime number">prime</a> p, and a generator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy">, she wants to prove that she knows a value x such that gx ≡ y (mod p), without revealing x. Indeed, knowledge of x could be used as a proof of identity, in that Peggy could have such knowledge because she chose a random value x that she did not reveal to anyone, computed y = gx mod p, and distributed the value of y to all potential verifiers, such that at a later time, proving knowledge of x is equivalent to proving identity as Peggy.

The protocol proceeds as follows: in each round, Peggy generates a random number r, computes C = gr mod p and discloses this to Victor. After receiving C, Victor randomly issues one of the following two requests: he either requests that Peggy discloses the value of r, or the value of (x + r) mod (p − 1).

Victor can verify either answer; if he requested r, he can then compute gr mod p and verify that it matches C. If he requested (x + r) mod (p − 1), then he can verify that C is consistent with this, by computing g(x + r) mod (p − 1) mod p and verifying that it matches (C · y) mod p. If Peggy indeed knows the value of x, then she can respond to either one of Victor's possible challenges.

If Peggy knew or could guess which challenge Victor is going to issue, then she could easily cheat and convince Victor that she knows x when she does not: if she knows that Victor is going to request r, then she proceeds normally: she picks r, computes C = gr mod p, and discloses C to Victor; she will be able to respond to Victor's challenge. On the other hand, if she knows that Victor will request (x + r) mod (p − 1), then she picks a random value r′, computes C′ ≡ gr′ · (gx)−1 mod p, and discloses C′ to Victor as the value of C that he is expecting. When Victor challenges her to reveal (x + r) mod (p − 1), she reveals r′, for which Victor will verify consistency, since he will in turn compute gr′ mod p, which matches C′ · y, since Peggy multiplied by the <a href="Modular_multiplicative_inverse" title="Modular multiplicative inverse">modular multiplicative inverse</a> of y.

However, if in either one of the above scenarios Victor issues a challenge other than the one she was expecting and for which she manufactured the result, then she will be unable to respond to the challenge under the assumption of infeasibility of solving the discrete log for this group. If she picked r and disclosed C = gr mod p, then she will be unable to produce a valid (x + r) mod (p − 1) that would pass Victor's verification, given that she does not know x. And if she picked a value r′ that poses as (x + r) mod (p − 1), then she would have to respond with the discrete log of the value that she disclosed – but Peggy does not know this discrete log, since the value C she disclosed was obtained through arithmetic with known values, and not by computing a power with a known exponent.

Thus, a cheating prover has a 0.5 probability of successfully cheating in one round. By executing a large-enough number of rounds, the probability of a cheating prover succeeding can be made arbitrarily low.

To show that the above interactive proof gives zero knowledge other than the fact that Peggy knows x, one can use similar arguments as used in the above proof of completeness and soundness. Specifically, a simulator, say Simon, who does not know x, can simulate the exchange between Peggy and Victor by the following procedure. Firstly, Simon randomly flips a fair coin. If the result is "heads", then he picks a random value r, computes C = gr mod p, and discloses C as if it is a message from Peggy to Victor. Then Simon also outputs a message "request the value of r" as if it is sent from Victor to Peggy, and immediately outputs the value of r as if it is sent from Peggy to Victor. A single round is complete. On the other hand, if the coin flipping result is "tails", then Simon picks a random number r′, computes C′ = gr′ · y−1 mod p, and discloses C′ as if it is a message from Peggy to Victor. Then Simon outputs "request the value of (x + r) mod (p − 1)" as if it is a message from Victor to Peggy. Finally, Simon outputs the value of r′ as if it is the response from Peggy back to Victor. A single round is complete. By the previous arguments when proving the completeness and soundness, the interactive communication simulated by Simon is indistinguishable from the true correspondence between Peggy and Victor. The zero-knowledge property is thus guaranteed.

<div class="mw-heading mw-heading3"><h3 id="Hamiltonian_cycle_for_a_large_graph">Hamiltonian cycle for a large graph</h3></div>

The following scheme is due to <a href="Manuel_Blum" title="Manuel Blum">Manuel Blum</a>.<a href="#cite_note-blum86-13">[13]</a>

In this scenario, Peggy knows a <a href="Hamiltonian_path" title="Hamiltonian path">Hamiltonian cycle</a> for a large <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> G. Victor knows G but not the cycle (e.g., Peggy has generated G and revealed it to him.) Finding a Hamiltonian cycle given a large graph is believed to be computationally infeasible, since its corresponding decision version is known to be <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>. Peggy will prove that she knows the cycle without simply revealing it (perhaps Victor is interested in buying it but wants verification first, or maybe Peggy is the only one who knows this information and is proving her identity to Victor).

To show that Peggy knows this Hamiltonian cycle, she and Victor play several rounds of a game:

<ul><li>At the beginning of each round, Peggy creates H, a graph which is <a href="Graph_isomorphism" title="Graph isomorphism">isomorphic</a> to G (that is, H is just like G except that all the vertices have different names). Since it is trivial to translate a Hamiltonian cycle between isomorphic graphs with known isomorphism, if Peggy knows a Hamiltonian cycle for G then she also must know one for H.</li>

<li>Peggy commits to H. She could do so by using a cryptographic <a href="Commitment_scheme" title="Commitment scheme">commitment scheme</a>. Alternatively, she could number the vertices of H. Next, for each edge of H, on a small piece of paper, she writes down the two vertices that the edge joins. Then she puts all these pieces of paper face down on a table. The purpose of this commitment is that Peggy is not able to change H while, at the same time, Victor has no information about H.</li>

<li>Victor then randomly chooses one of two questions to ask Peggy. He can either ask her to show the isomorphism between H and G (see <a href="Graph_isomorphism_problem" title="Graph isomorphism problem">graph isomorphism problem</a>), or he can ask her to show a Hamiltonian cycle in H.</li>

<li>If Peggy is asked to show that the two graphs are isomorphic, then she first uncovers all of H (e.g. by turning over all pieces of papers that she put on the table) and then provides the vertex translations that map G to H. Victor can verify that they are indeed isomorphic.</li>

<li>If Peggy is asked to prove that she knows a Hamiltonian cycle in H, then she translates her Hamiltonian cycle in G onto H and only uncovers the edges on the Hamiltonian cycle. That is, Peggy only turns over exactly |V(G)| of the pieces of paper that correspond to the edges of the Hamiltonian cycle, while leaving the rest still face-down. This is enough for Victor to check that H does indeed contain a Hamiltonian cycle.</li></ul>

It is important that the commitment to the graph be such that Victor can verify, in the second case, that the cycle is really made of edges from H. This can be done by, for example, committing to every edge (or lack thereof) separately.

<div class="mw-heading mw-heading4"><h4 id="Completeness">Completeness</h4></div>

If Peggy does know a Hamiltonian cycle in G, then she can easily satisfy Victor's demand for either the graph isomorphism producing H from G (which she had committed to in the first step) or a Hamiltonian cycle in H (which she can construct by applying the isomorphism to the cycle in G).

<div class="mw-heading mw-heading4"><h4 id="Zero-knowledge">Zero-knowledge</h4></div>

Peggy's answers do not reveal the original Hamiltonian cycle in G. In each round, Victor will learn only H's isomorphism to G or a Hamiltonian cycle in H. He would need both answers for a single H to discover the cycle in G, so the information remains unknown as long as Peggy can generate a distinct H every round. If Peggy does not know of a Hamiltonian cycle in G, but somehow knew in advance what Victor would ask to see each round, then she could cheat. For example, if Peggy knew ahead of time that Victor would ask to see the Hamiltonian cycle in H, then she could generate a Hamiltonian cycle for an unrelated graph. Similarly, if Peggy knew in advance that Victor would ask to see the isomorphism then she could simply generate an isomorphic graph H (in which she also does not know a Hamiltonian cycle). Victor could simulate the protocol by himself (without Peggy) because he knows what he will ask to see. Therefore, Victor gains no information about the Hamiltonian cycle in G from the information revealed in each round.

<div class="mw-heading mw-heading4"><h4 id="Soundness">Soundness</h4></div>

If Peggy does not know the information, then she can guess which question Victor will ask and generate either a graph isomorphic to G or a Hamiltonian cycle for an unrelated graph, but since she does not know a Hamiltonian cycle for G, she cannot do both. With this guesswork, her chance of fooling Victor is 2−<var style="padding-right: 1px;">n</var>, where n is the number of rounds. For all realistic purposes, it is infeasibly difficult to defeat a zero-knowledge proof with a reasonable number of rounds in this way.

<div class="mw-heading mw-heading2"><h2 id="Variants_of_zero-knowledge">Variants of zero-knowledge</h2></div>

Different variants of zero-knowledge can be defined by formalizing the intuitive concept of what is meant by the output of the simulator "looking like" the execution of the real proof protocol in the following ways:

<ul><li>We speak of perfect zero-knowledge if the distributions produced by the simulator and the proof protocol are distributed exactly the same. This is for instance the case in the first example above.</li>

<li>Statistical zero-knowledge<a href="#cite_note-14">[14]</a> means that the distributions are not necessarily exactly the same, but they are <a href="Statistically_close" class="mw-redirect" title="Statistically close">statistically close</a>, meaning that their statistical difference is a <a href="Negligible_function" title="Negligible function">negligible function</a>.</li>

<li>We speak of computational zero-knowledge if no efficient algorithm can distinguish the two distributions.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Zero_knowledge_types">Zero knowledge types</h2></div>

There are various types of zero-knowledge proofs:

<ul><li><a href="Proof_of_knowledge" title="Proof of knowledge">Proof of knowledge</a>: the knowledge is hidden in the exponent like in the example shown above.</li>

<li><a href="Witness-indistinguishable_proof" title="Witness-indistinguishable proof">Witness-indistinguishable proof</a>: verifiers cannot know which witness is used for producing the proof.</li></ul>

Zero-knowledge proof schemes can be constructed from various cryptographic primitives, such as <a href="Hash-based_cryptography" title="Hash-based cryptography">hash-based cryptography</a>, <a href="Pairing-based_cryptography" title="Pairing-based cryptography">pairing-based cryptography</a>, <a href="Multi-party_computation" class="mw-redirect" title="Multi-party computation">multi-party computation</a>, or <a href="Lattice-based_cryptography" title="Lattice-based cryptography">lattice-based cryptography</a>.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Authentication_systems">Authentication systems</h3></div>

Research in zero-knowledge proofs has been motivated by <a href="Authentication" title="Authentication">authentication</a> systems where one party wants to prove its identity to a second party via some secret information (such as a password) but does not want the second party to learn anything about this secret. This is called a "zero-knowledge <a href="Proof_of_knowledge" title="Proof of knowledge">proof of knowledge</a>". However, a password is typically too small or insufficiently random to be used in many schemes for zero-knowledge proofs of knowledge. A <a href="Zero-knowledge_password_proof" title="Zero-knowledge password proof">zero-knowledge password proof</a> is a special kind of zero-knowledge proof of knowledge that addresses the limited size of passwords.

In April 2015, the one-out-of-many proofs protocol (a <a href="Proof_of_knowledge#Sigma_protocols" title="Proof of knowledge">Sigma protocol</a>) was introduced.<a href="#cite_note-:1-15">[15]</a> In August 2021, <a href="Cloudflare" title="Cloudflare">Cloudflare</a>, an American web infrastructure and security company, decided to use the one-out-of-many proofs mechanism for private web verification using vendor hardware.<a href="#cite_note-16">[16]</a>

<div class="mw-heading mw-heading3"><h3 id="Ethical_behavior">Ethical behavior</h3></div>

One of the uses of zero-knowledge proofs within cryptographic protocols is to enforce honest behavior while maintaining privacy. Roughly, the idea is to force a user to prove, using a zero-knowledge proof, that its behavior is correct according to the protocol.<a href="#cite_note-knowledgecomplexity-17">[17]</a><a href="#cite_note-18">[18]</a> Because of soundness, we know that the user must really act honestly in order to be able to provide a valid proof. Because of zero knowledge, we know that the user does not compromise the privacy of its secrets in the process of providing the proof.

<div class="mw-heading mw-heading3"><h3 id="Nuclear_disarmament">Nuclear disarmament</h3></div>

In 2016, the <a href="Princeton_Plasma_Physics_Laboratory" title="Princeton Plasma Physics Laboratory">Princeton Plasma Physics Laboratory</a> and <a href="Princeton_University" title="Princeton University">Princeton University</a> demonstrated a technique that may have applicability to future <a href="Nuclear_disarmament" title="Nuclear disarmament">nuclear disarmament</a> talks. It would allow inspectors to confirm whether or not an object is indeed a nuclear weapon without recording, sharing, or revealing the internal workings, which might be secret.<a href="#cite_note-19">[19]</a>

<div class="mw-heading mw-heading3"><h3 id="Blockchains">Blockchains</h3></div>

Zero-knowledge proofs were applied in the <a href="Zerocoin_protocol" title="Zerocoin protocol">Zerocoin</a> and Zerocash protocols, which culminated in the birth of <a href="Zcoin" class="mw-redirect" title="Zcoin">Zcoin</a><a href="#cite_note-Hellwig_2020-20">[20]</a> (later rebranded as <a href="Firo_(cryptocurrency)" title="Firo (cryptocurrency)">Firo</a> in 2020)<a href="#cite_note-21">[21]</a> and <a href="Zcash" title="Zcash">Zcash</a> cryptocurrencies in 2016. Zerocoin has a built-in mixing model that does not trust any peers or centralised mixing providers to ensure anonymity.<a href="#cite_note-Hellwig_2020-20">[20]</a> Users can transact in a base currency and can cycle the currency into and out of Zerocoins.<a href="#cite_note-22">[22]</a> The Zerocash protocol uses a similar model (a variant known as a <a href="Non-interactive_zero-knowledge_proof" title="Non-interactive zero-knowledge proof">non-interactive zero-knowledge proof</a>)<a href="#cite_note-23">[23]</a> except that it can obscure the transaction amount, while Zerocoin cannot. Given significant restrictions of transaction data on the Zerocash network, Zerocash is less prone to privacy timing attacks when compared to Zerocoin. However, this additional layer of privacy can cause potentially undetected hyperinflation of Zerocash supply because fraudulent coins cannot be tracked.<a href="#cite_note-Hellwig_2020-20">[20]</a><a href="#cite_note-24">[24]</a>

In 2018, Bulletproofs were introduced. Bulletproofs are an improvement from non-interactive zero-knowledge proofs where a trusted setup is not needed.<a href="#cite_note-Bulletproofs-25">[25]</a> It was later implemented into the Mimblewimble protocol (which the Grin and Beam cryptocurrencies are based upon) and <a href="Monero_(cryptocurrency)" class="mw-redirect" title="Monero (cryptocurrency)">Monero cryptocurrency</a>.<a href="#cite_note-26">[26]</a> In 2019, Firo implemented the Sigma protocol, which is an improvement on the Zerocoin protocol without trusted setup.<a href="#cite_note-27">[27]</a><a href="#cite_note-:1-15">[15]</a> In the same year, Firo introduced the Lelantus protocol, an improvement on the Sigma protocol, where the former hides the origin and amount of a transaction.<a href="#cite_note-28">[28]</a>

A related line of work applies zero-knowledge proofs to database analytics via so-called zero-knowledge “coprocessors”: off-chain systems that execute queries and return both the result and a proof that the computation was performed correctly on untampered data. Academic prototypes have shown how to produce ZK proofs for ad-hoc SQL queries while hiding inputs and guaranteeing correctness of the result (e.g., ZKSQL).<a href="#cite_note-29">[29]</a> One implementation of this approach, termed “Proof of SQL”, has been reported in industry media as enabling sub-second ZK proving for SQL query results and making the prover available as open source.<a href="#cite_note-30">[30]</a><a href="#cite_note-31">[31]</a> Earlier coverage also described the concept under development as a cryptographic protocol allowing decentralized applications to verify that SQL results have not been tampered with.<a href="#cite_note-32">[32]</a><a href="#cite_note-33">[33]</a>

<div class="mw-heading mw-heading3"><h3 id="Decentralized_Identifiers">Decentralized Identifiers</h3></div>

Zero-knowledge proofs by their nature can enhance privacy in identity-sharing systems, which are vulnerable to data breaches and identity theft. When integrated to a <a href="Decentralized_identifier" title="Decentralized identifier">decentralized identifier</a> system, ZKPs add an extra layer of encryption on DID documents.<a href="#cite_note-34">[34]</a>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

Zero-knowledge proofs were first conceived in 1985 by <a href="Shafi_Goldwasser" title="Shafi Goldwasser">Shafi Goldwasser</a>, <a href="Silvio_Micali" title="Silvio Micali">Silvio Micali</a>, and <a href="Charles_Rackoff" title="Charles Rackoff">Charles Rackoff</a> in their paper "The Knowledge Complexity of Interactive Proof-Systems".<a href="#cite_note-knowledgecomplexity-17">[17]</a> This paper introduced the IP hierarchy of interactive proof systems (see <a href="Interactive_proof_system" title="Interactive proof system">interactive proof system</a>) and conceived the concept of knowledge complexity, a measurement of the amount of knowledge about the proof transferred from the prover to the verifier. They also gave the first zero-knowledge proof for a concrete problem, that of deciding <a href="Quadratic_residue" title="Quadratic residue">quadratic nonresidues</a> mod <var style="padding-right: 1px;">m</var>. Together with a paper by <a href="L%C3%A1szl%C3%B3_Babai" title="László Babai">László Babai</a> and <a href="Shlomo_Moran" title="Shlomo Moran">Shlomo Moran</a>, this landmark paper invented interactive proof systems, for which all five authors won the first <a href="G%C3%B6del_Prize" title="Gödel Prize">Gödel Prize</a> in 1993.

In their own words, Goldwasser, Micali, and Rackoff say:

Of particular interest is the case where this additional knowledge is essentially 0 and we show that [it] is possible to interactively prove that a number is quadratic non residue mod m releasing 0 additional knowledge. This is surprising as no efficient algorithm for deciding quadratic residuosity mod m is known when m’s factorization is not given. Moreover, all known NP proofs for this problem exhibit the prime factorization of m. This indicates that adding interaction to the proving process, may decrease the amount of knowledge that must be communicated in order to prove a theorem.

</blockquote>

The quadratic nonresidue problem has both an <a href="NP_(complexity)" title="NP (complexity)">NP</a> and a <a href="Co-NP" title="Co-NP">co-NP</a> algorithm, and so lies in the intersection of NP and co-NP. This was also true of several other problems for which zero-knowledge proofs were subsequently discovered, such as an unpublished proof system by Oded Goldreich verifying that a two-prime modulus is not a <a href="Blum_integer" title="Blum integer">Blum integer</a>.<a href="#cite_note-35">[35]</a>

<a href="Oded_Goldreich" title="Oded Goldreich">Oded Goldreich</a>, <a href="Silvio_Micali" title="Silvio Micali">Silvio Micali</a>, and <a href="Avi_Wigderson" title="Avi Wigderson">Avi Wigderson</a> took this one step further, showing that, assuming the existence of unbreakable encryption, one can create a zero-knowledge proof system for the NP-complete <a href="Graph_coloring_problem" class="mw-redirect" title="Graph coloring problem">graph coloring problem</a> with three colors. Since every problem in NP can be efficiently reduced to this problem, this means that, under this assumption, all problems in NP have zero-knowledge proofs.<a href="#cite_note-36">[36]</a> The reason for the assumption is that, as in the above example, their protocols require encryption. A commonly cited sufficient condition for the existence of unbreakable encryption is the existence of <a href="One-way_function" title="One-way function">one-way functions</a>, but it is conceivable that some physical means might also achieve it.

On top of this, they also showed that the <a href="Graph_nonisomorphism_problem" class="mw-redirect" title="Graph nonisomorphism problem">graph nonisomorphism problem</a>, the <a href="Complement_(complexity)" title="Complement (complexity)">complement</a> of the <a href="Graph_isomorphism_problem" title="Graph isomorphism problem">graph isomorphism problem</a>, has a zero-knowledge proof. This problem is in co-NP, but is not currently known to be in either NP or any practical class. More generally, <a href="Russell_Impagliazzo" title="Russell Impagliazzo">Russell Impagliazzo</a> and <a href="Moti_Yung" title="Moti Yung">Moti Yung</a> as well as Ben-Or et al. would go on to show that, also assuming one-way functions or unbreakable encryption, there are zero-knowledge proofs for all problems in IP = PSPACE, or in other words, anything that can be proved by an interactive proof system can be proved with zero knowledge.<a href="#cite_note-37">[37]</a><a href="#cite_note-38">[38]</a>

Not liking to make unnecessary assumptions, many theorists sought a way to eliminate the necessity of <a href="One_way_function" class="mw-redirect" title="One way function">one way functions</a>. One way this was done was with multi-prover interactive proof systems (see <a href="Interactive_proof_system" title="Interactive proof system">interactive proof system</a>), which have multiple independent provers instead of only one, allowing the verifier to "cross-examine" the provers in isolation to avoid being misled. It can be shown that, without any intractability assumptions, all languages in NP have zero-knowledge proofs in such a system.<a href="#cite_note-39">[39]</a>

It turns out that, in an Internet-like setting, where multiple protocols may be executed concurrently, building zero-knowledge proofs is more challenging. The line of research investigating concurrent zero-knowledge proofs was initiated by the work of <a href="Cynthia_Dwork" title="Cynthia Dwork">Dwork</a>, <a href="Moni_Naor" title="Moni Naor">Naor</a>, and <a href="Amit_Sahai" title="Amit Sahai">Sahai</a>.<a href="#cite_note-40">[40]</a> One particular development along these lines has been the development of <a href="Witness-indistinguishable_proof" title="Witness-indistinguishable proof">witness-indistinguishable proof</a> protocols. The property of witness-indistinguishability is related to that of zero-knowledge, yet witness-indistinguishable protocols do not suffer from the same problems of concurrent execution.<a href="#cite_note-41">[41]</a>

Another variant of zero-knowledge proofs are <a href="Non-interactive_zero-knowledge_proof" title="Non-interactive zero-knowledge proof">non-interactive zero-knowledge proofs</a>. Blum, Feldman, and Micali showed that a common random string shared between the prover and the verifier is enough to achieve computational zero-knowledge without requiring interaction.<a href="#cite_note-noninteractive-5">[5]</a><a href="#cite_note-noninteractive2-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Zero-Knowledge_Proof_protocols">Zero-Knowledge Proof protocols</h2></div>

The most popular interactive or <a href="Non-interactive_zero-knowledge_proof" title="Non-interactive zero-knowledge proof">non-interactive zero-knowledge proof</a> (e.g., zk-SNARK) protocols can be broadly categorized in the following four categories: Succinct Non-Interactive ARguments of Knowledge (SNARK), Scalable Transparent ARgument of Knowledge (STARK), Verifiable Polynomial Delegation (VPD), and Succinct Non-interactive ARGuments (SNARG). A list of zero-knowledge proof protocols and libraries is provided below along with comparisons based on transparency, universality, plausible post-quantum security, and programming paradigm.<a href="#cite_note-mouris21-42">[42]</a> A transparent protocol is one that does not require any trusted setup and uses public randomness. A universal protocol is one that does not require a separate trusted setup for each circuit. Finally, a plausibly post-quantum protocol is one that is not susceptible to known attacks involving quantum algorithms.

<caption>Zero-knowledge proof (ZKP) systems

</caption>

<th>ZKP System</th>

<th>Publication year</th>

<th>Protocol</th>

<th>Transparent</th>

<th>Universal</th>

<th>Plausibly Post-Quantum Secure</th>

<th>Programming Paradigm

</th></tr>

<tr>

<td>Pinocchio<a href="#cite_note-43">[43]</a></td>

<td>zk-SNARK</td>

<td>Procedural

</td></tr>

<tr>

<td>Geppetto<a href="#cite_note-44">[44]</a></td>

<td>zk-SNARK</td>

<td>Procedural

</td></tr>

<tr>

<td>TinyRAM<a href="#cite_note-45">[45]</a></td>

<td>zk-SNARK</td>

<td>Procedural

</td></tr>

<tr>

<td>Buffet<a href="#cite_note-46">[46]</a></td>

<td>zk-SNARK</td>

<td>Procedural

</td></tr>

<tr>

<td>ZoKrates<a href="#cite_note-47">[47]</a></td>

<td>zk-SNARK</td>

<td>Procedural

</td></tr>

<tr>

<td>xJsnark<a href="#cite_note-48">[48]</a></td>

<td>zk-SNARK</td>

<td>Procedural

</td></tr>

<tr>

<td>zk-SNARG</td>

<td>Assembly

</td></tr>

<tr>

<td>vnTinyRAM<a href="#cite_note-50">[50]</a></td>

<td>zk-SNARK</td>

<td>Procedural

</td></tr>

<tr>

<td>MIRAGE<a href="#cite_note-51">[51]</a></td>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>Sonic<a href="#cite_note-52">[52]</a></td>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>Marlin<a href="#cite_note-53">[53]</a></td>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>PLONK<a href="#cite_note-54">[54]</a></td>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>SuperSonic<a href="#cite_note-55">[55]</a></td>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>Bulletproofs<a href="#cite_note-Bulletproofs-25">[25]</a></td>

<td>Bulletproofs</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>Hyrax<a href="#cite_note-56">[56]</a></td>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>Virgo<a href="#cite_note-58">[58]</a></td>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>Ligero<a href="#cite_note-59">[59]</a></td>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>Aurora<a href="#cite_note-60">[60]</a></td>

<td>zk-SNARK</td>

<td>Arithmetic Circuits

</td></tr>

<tr>

<td>zk-STARK<a href="#cite_note-61">[61]</a></td>

<td>zk-STARK</td>

<td>Assembly

</td></tr>

<tr>

<td>Zilch<a href="#cite_note-mouris21-42">[42]</a></td>

<td>zk-STARK</td>

<td>Object-Oriented

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Security_vulnerabilities_of_zero-knowledge_systems">Security vulnerabilities of zero-knowledge systems</h2></div>

While zero-knowledge proofs offer a secure way to verify information, the arithmetic circuits that implement them must be carefully designed. If these circuits lack sufficient constraints, they may introduce subtle yet critical security vulnerabilities.

One of the most common classes of vulnerabilities in these systems is under-constrained logic, where insufficient constraints allow a malicious prover to produce a proof for an incorrect statement that still passes verification. A 2024 systematization of known attacks found that approximately 96% of documented circuit-layer bugs in SNARK-based systems were due to under-constrained circuits.<a href="#cite_note-62">[62]</a>

These vulnerabilities often arise during the translation of high-level logic into low-level constraint systems, particularly when using domain-specific languages such as Circom or Gnark. Recent research has demonstrated that formally proving determinism – ensuring that a circuit's outputs are uniquely determined by its inputs – can eliminate entire classes of these vulnerabilities.<a href="#cite_note-63">[63]</a>

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col">

<ul><li><a href="Arrow_information_paradox" title="Arrow information paradox">Arrow information paradox</a> – Problem in intellectual property management</li>

<li><a href="Cryptographic_protocol" title="Cryptographic protocol">Cryptographic protocol</a> – Aspect of cryptography</li>

<li><a href="Feige%E2%80%93Fiat%E2%80%93Shamir_identification_scheme" title="Feige–Fiat–Shamir identification scheme">Feige–Fiat–Shamir identification scheme</a></li>

<li><a href="Probabilistically_checkable_proof" title="Probabilistically checkable proof">Probabilistically checkable proof</a> – Proof checkable by a randomized algorithm</li>

<li><a href="Proof_of_knowledge" title="Proof of knowledge">Proof of knowledge</a> – Class of interactive proof</li>

<li><a href="Topics_in_cryptography" class="mw-redirect" title="Topics in cryptography">Topics in cryptography</a></li>

<li><a href="Witness-indistinguishable_proof" title="Witness-indistinguishable proof">Witness-indistinguishable proof</a> – Variant of a zero-knowledge proof for languages in NP</li>

<li><a href="Zero-knowledge_password_proof" title="Zero-knowledge password proof">Zero-knowledge password proof</a> – Cryptographic protocol</li>

<li><a href="Non-interactive_zero-knowledge_proof" title="Non-interactive zero-knowledge proof">Non-interactive zero-knowledge proof</a> – Cryptographic primitive</li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=fOGdb1CTu5c">Computer scientist Amit Sahai explains the Zero-knowledge proof in 5 Levels of Difficulty</a> on <a href="YouTube_video_(identifier)" class="mw-redirect" title="YouTube video (identifier)">YouTube</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAad2023" class="citation cs2">Aad, Imad (2023), Mulder, Valentin; Mermoud, Alain; Lenders, Vincent; Tellenbach, Bernhard (eds.), "Zero-Knowledge Proof", Trends in Data Protection and Encryption Technologies, Cham: Springer Nature Switzerland, pp. 25–30, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-031-33386-6_6">10.1007/978-3-031-33386-6_6</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-031-33386-6</bdi></cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFGoldreich2001" class="citation book cs1">Goldreich, Oded (2001). <a rel="nofollow" class="external text" href="https://www.cambridge.org/core/books/foundations-of-cryptography/B61B6AD235D2034D511A5FF740415166">Foundations of Cryptography Volume I</a>. Cambridge University Press. p. 184. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9780511546891">10.1017/CBO9780511546891</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780511546891</bdi>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFGoldreich2001" class="citation book cs1">Goldreich, Oded (2001). <a rel="nofollow" class="external text" href="https://www.cambridge.org/core/books/foundations-of-cryptography/B61B6AD235D2034D511A5FF740415166">Foundations of Cryptography Volume I</a>. Cambridge University Press. p. 247. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9780511546891">10.1017/CBO9780511546891</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780511546891</bdi>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFGoldreich2001" class="citation book cs1">Goldreich, Oded (2001). <a rel="nofollow" class="external text" href="https://www.cambridge.org/core/books/foundations-of-cryptography/B61B6AD235D2034D511A5FF740415166">Foundations of Cryptography Volume I</a>. Cambridge University Press. p. 299. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9780511546891">10.1017/CBO9780511546891</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780511546891</bdi>.</cite>

</li>

<li id="cite_note-noninteractive-5">^ <a href="#cite_ref-noninteractive_5-0">a</a> <a href="#cite_ref-noninteractive_5-1">b</a> <cite id="CITEREFBlumFeldmanMicali1988" class="citation book cs1">Blum, Manuel; Feldman, Paul; Micali, Silvio (1988). "Non-interactive zero-knowledge and its applications". <a rel="nofollow" class="external text" href="https://apps.dtic.mil/sti/pdfs/ADA222698.pdf">Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88</a> (PDF). pp. 103–112. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F62212.62222">10.1145/62212.62222</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0897912648</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7282320">7282320</a>. <a rel="nofollow" class="external text" href="https://wayback.archive-it.org/all/20181214020301/https://apps.dtic.mil/dtic/tr/fulltext/u2/a222698.pdf">Archived</a> (PDF) from the original on December 14, 2018. Retrieved June 2, 2022.</cite>

</li>

<li id="cite_note-noninteractive2-6">^ <a href="#cite_ref-noninteractive2_6-0">a</a> <a href="#cite_ref-noninteractive2_6-1">b</a> <cite id="CITEREFWuWang2014" class="citation journal cs1">Wu, Huixin; Wang, Feng (2014). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4032740">"A Survey of Noninteractive Zero Knowledge Proof System and Its Applications"</a>. The Scientific World Journal. 2014: 560484. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1155%2F2014%2F560484">10.1155/2014/560484</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4032740">4032740</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/24883407">24883407</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://fouryears.eu/2015/03/09/playing-card-cryptography/">"Playing Card Cryptography"</a>. Four Years Remaining. Retrieved 2025-06-04.</cite>

</li>

<li id="cite_note-Murtagh-8">^ <a href="#cite_ref-Murtagh_8-0">a</a> <a href="#cite_ref-Murtagh_8-1">b</a> <a href="#cite_ref-Murtagh_8-2">c</a> <cite id="CITEREFMurtagh2023" class="citation news cs1">Murtagh, Jack (July 1, 2023). <a rel="nofollow" class="external text" href="https://www.scientificamerican.com/article/wheres-waldo-how-to-prove-you-found-him-without-revealing-where-he-is/">"Where's Wally? How to Mathematically Prove You Found Him without Revealing Where He Is"</a>. <a href="Scientific_American" title="Scientific American">Scientific American</a>. Retrieved 2023-10-02.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFQuisquaterGuillouBerson1990" class="citation book cs1">Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). "How to Explain Zero-Knowledge Protocols to Your Children". <a rel="nofollow" class="external text" href="http://www.cs.wisc.edu/~mkowalcz/628.pdf">Advances in Cryptology — CRYPTO' 89 Proceedings</a> (PDF). Lecture Notes in Computer Science. Vol. 435. pp. 628–631. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F0-387-34805-0_60">10.1007/0-387-34805-0_60</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-97317-3</bdi>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFChalkias" class="citation news cs1">Chalkias, Konstantinos. <a rel="nofollow" class="external text" href="https://www.linkedin.com/pulse/demonstrate-how-zero-knowledge-proofs-work-without-using-chalkias">"Demonstrate how Zero-Knowledge Proofs work without using maths"</a>. CordaCon 2017. Retrieved 2017-09-13.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFFeigeFiatShamir1988" class="citation journal cs1">Feige, Uriel; Fiat, Amos; Shamir, Adi (1988-06-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02351717">"Zero-knowledge proofs of identity"</a>. Journal of Cryptology. 1 (2): 77–94. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02351717">10.1007/BF02351717</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1432-1378">1432-1378</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2950602">2950602</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFChaumEvertsevan_de_Graaf1988" class="citation book cs1">Chaum, David; Evertse, Jan-Hendrik; van de Graaf, Jeroen (1988). "An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations". Advances in Cryptology — EUROCRYPT '87. Lecture Notes in Computer Science. Vol. 304. pp. 127–141. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-39118-5_13">10.1007/3-540-39118-5_13</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-19102-5</bdi>.</cite>

</li>

<li id="cite_note-blum86-13"><a href="#cite_ref-blum86_13-0">^</a> <cite id="CITEREFBlum1986" class="citation journal cs1">Blum, Manuel (1986). <a rel="nofollow" class="external text" href="http://euler.nmt.edu/~brian/students/pope.pdf">"How to Prove a Theorem So No One Else Can Claim It"</a> (PDF). ICM Proceedings: 1444–1451. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.469.9048">10.1.1.469.9048</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230103032937/http://euler.nmt.edu/~brian/students/pope.pdf">Archived</a> (PDF) from the original on January 3, 2023.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFSahaiVadhan2003" class="citation journal cs1">Sahai, Amit; Vadhan, Salil (1 March 2003). <a rel="nofollow" class="external text" href="http://dash.harvard.edu/bitstream/handle/1/4728406/Vadhan_StatZeroKnow.pdf?sequence=2">"A complete problem for statistical zero knowledge"</a> (PDF). Journal of the ACM. 50 (2): 196–249. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.3957">10.1.1.4.3957</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F636865.636868">10.1145/636865.636868</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:218593855">218593855</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150625193124/http://dash.harvard.edu/bitstream/handle/1/4728406/Vadhan_StatZeroKnow.pdf?sequence=2">Archived</a> (PDF) from the original on 2015-06-25.</cite>

</li>

<li id="cite_note-:1-15">^ <a href="#cite_ref-:1_15-0">a</a> <a href="#cite_ref-:1_15-1">b</a> <cite id="CITEREFGrothKohlweiss2015" class="citation book cs1">Groth, J; Kohlweiss, M (14 April 2015). <a rel="nofollow" class="external text" href="https://www.research.ed.ac.uk/en/publications/f6ec5d8f-cfda-4f56-9bd0-d9222b8d9a43">"One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin"</a>. Advances in Cryptology - EUROCRYPT 2015. Lecture Notes in Computer Science. Vol. 9057. Berlin, Heidelberg: EUROCRYPT 2015. pp. 253–280. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-662-46803-6_9">10.1007/978-3-662-46803-6_9</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/20.500.11820%2Ff6ec5d8f-cfda-4f56-9bd0-d9222b8d9a43">20.500.11820/f6ec5d8f-cfda-4f56-9bd0-d9222b8d9a43</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-662-46802-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16708805">16708805</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://blog.cloudflare.com/introducing-zero-knowledge-proofs-for-private-web-attestation-with-cross-multi-vendor-hardware/">"Introducing Zero-Knowledge Proofs for Private Web attestation with Cross/Multi-Vendor Hardware"</a>. The Cloudflare Blog. 2021-08-12. Retrieved 2021-08-18.</cite>

</li>

<li id="cite_note-knowledgecomplexity-17">^ <a href="#cite_ref-knowledgecomplexity_17-0">a</a> <a href="#cite_ref-knowledgecomplexity_17-1">b</a> <cite id="CITEREFGoldwasserMicaliRackoff1989" class="citation cs2">Goldwasser, S.; Micali, S.; Rackoff, C. (1989), <a rel="nofollow" class="external text" href="http://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf">"The knowledge complexity of interactive proof systems"</a> (PDF), SIAM Journal on Computing, 18 (1): 186–208, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0218012">10.1137/0218012</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1095-7111">1095-7111</a></cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFAbascalFaghihi_SereshgiHazayIshai2020" class="citation book cs1">Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (2020-10-30). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3372297.3423366">"Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC"</a>. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. CCS '20. Virtual Event, USA: Association for Computing Machinery. pp. 1591–1605. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3372297.3423366">10.1145/3372297.3423366</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-7089-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:226228208">226228208</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170703142802/https://www.pppl.gov/news/2016/09/pppl-and-princeton-demonstrate-novel-technique-may-have-applicability-future-nuclear">"PPPL and Princeton demonstrate novel technique that may have applicability to future nuclear disarmament talks - Princeton Plasma Physics Lab"</a>. www.pppl.gov. Archived from <a rel="nofollow" class="external text" href="http://www.pppl.gov/news/2016/09/pppl-and-princeton-demonstrate-novel-technique-may-have-applicability-future-nuclear">the original</a> on 2017-07-03.</cite>

</li>

<li id="cite_note-Hellwig_2020-20">^ <a href="#cite_ref-Hellwig_2020_20-0">a</a> <a href="#cite_ref-Hellwig_2020_20-1">b</a> <a href="#cite_ref-Hellwig_2020_20-2">c</a> <cite id="CITEREFHellwigKarlicHuchzermeier2020" class="citation book cs1">Hellwig, Daniel; Karlic, Goran; Huchzermeier, Arnd (3 May 2020). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-030-40142-9_5">"Privacy and Anonymity"</a>. Build Your Own Blockchain. Management for Professionals. SpringerLink. p. 112. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-40142-9_5">10.1007/978-3-030-40142-9_5</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783030401429</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:219058406">219058406</a>. Retrieved 3 December 2020.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFHurst2020" class="citation web cs1">Hurst, Samantha (28 October 2020). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20201101141745/https://www.crowdfundinsider.com/2020/10/168504-zcoin-announces-rebranding-to-new-name-ticker-firo/">"Zcoin Announces Rebranding to New Name & Ticker "Firo""</a>. Crowdfund Insider. Archived from <a rel="nofollow" class="external text" href="https://www.crowdfundinsider.com/2020/10/168504-zcoin-announces-rebranding-to-new-name-ticker-firo/">the original</a> on 1 November 2020. Retrieved 4 November 2020.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFBonneauMillerClarkNarayanan2015" class="citation book cs1">Bonneau, J; Miller, A; Clark, J; Narayanan, A (2015). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/7163021">"SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies"</a>. 2015 IEEE Symposium on Security and Privacy. San Jose, California. pp. 104–121. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSP.2015.14">10.1109/SP.2015.14</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4673-6949-7</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:549362">549362</a>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: location missing publisher (link)

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFBen-SassonChiesaGarmanGreen2014" class="citation web cs1">Ben-Sasson, Eli; Chiesa, Alessandro; Garman, Christina; Green, Matthew; Miers, Ian; Tromer, Eran; Virza, Madars (18 May 2014). <a rel="nofollow" class="external text" href="http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf">"Zerocash: Decentralized Anonymous Payments from Bitcoin"</a> (PDF). IEEE. Retrieved 26 January 2016.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFOrcutt" class="citation news cs1">Orcutt, Mike. <a rel="nofollow" class="external text" href="https://www.technologyreview.com/s/609448/a-mind-bending-cryptographic-trick-promises-to-take-blockchains-mainstream">"A mind-bending cryptographic trick promises to take blockchains mainstream"</a>. MIT Technology Review. Retrieved 2017-12-18.</cite>

</li>

<li id="cite_note-Bulletproofs-25">^ <a href="#cite_ref-Bulletproofs_25-0">a</a> <a href="#cite_ref-Bulletproofs_25-1">b</a> <cite id="CITEREFBünzBootleBoneh2018" class="citation book cs1">Bünz, B; Bootle, D; Boneh, A (2018). "Bulletproofs: Short Proofs for Confidential Transactions and More". 2018 IEEE Symposium on Security and Privacy (SP). San Francisco, California. pp. 315–334. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSP.2018.00020">10.1109/SP.2018.00020</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-5386-4353-2</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3337741">3337741</a>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: location missing publisher (link)

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFOdendaalSharrockHeerden" class="citation web cs1">Odendaal, Hansie; Sharrock, Cayle; Heerden, SW. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200929160834/https://tlu.tarilabs.com/cryptography/bulletproofs-and-mimblewimble/MainReport.html">"Bulletproofs and Mimblewimble"</a>. Tari Labs University. Archived from <a rel="nofollow" class="external text" href="https://tlu.tarilabs.com/cryptography/bulletproofs-and-mimblewimble/MainReport.html#current-and-past-efforts">the original</a> on 29 September 2020. Retrieved 3 December 2020.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFAndrew2019" class="citation news cs1">Andrew, Munro (30 July 2019). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190730210721/https://www.finder.com.au/zcoin-cryptocurrency-introduces-zero-knowledge-proofs-with-no-trusted-setup">"Zcoin cryptocurrency introduces zero knowledge proofs with no trusted set-up"</a>. Finder Australia. Archived from <a rel="nofollow" class="external text" href="https://www.finder.com.au/zcoin-cryptocurrency-introduces-zero-knowledge-proofs-with-no-trusted-setup">the original</a> on 30 July 2019. Retrieved 30 July 2019.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFAram2019" class="citation journal cs1">Aram, Jivanyan (7 April 2019). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2019/373">"Lelantus: Towards Confidentiality and Anonymity of Blockchain Transactions from Standard Assumptions"</a>. Cryptology ePrint Archive (Report 373). Retrieved 14 April 2019.</cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite id="CITEREFLiothers2023" class="citation journal cs1">Li, X.; others (2023). <a rel="nofollow" class="external text" href="https://www.vldb.org/pvldb/vol16/p1804-li.pdf">"ZKSQL: Verifiable and Efficient Query Evaluation with Zero-Knowledge Proofs"</a> (PDF). Proceedings of the VLDB Endowment. 16: 1804–1817.</cite>

</li>

<li id="cite_note-30"><a href="#cite_ref-30">^</a> <cite class="citation news cs1"><a rel="nofollow" class="external text" href="https://www.coindesk.com/tech/2024/06/11/protocol-village">"Protocol Village: Space and Time Releases 'Proof of SQL v1' With Sub-Second ZK Prover"</a>. CoinDesk. 12 June 2024.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite class="citation news cs1"><a rel="nofollow" class="external text" href="https://cointelegraph.com/news/open-source-zk-proof-slashes-sql-query-times-sub-seconds">"New open-source ZK-proof slashes SQL query times"</a>. Cointelegraph. 12 June 2024.</cite>

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite id="CITEREFBetz2022" class="citation news cs1">Betz, Brandy (28 July 2022). <a rel="nofollow" class="external text" href="https://www.coindesk.com/business/2022/07/28/decentralized-data-platform-space-and-time-raises-10m">"Decentralized Data Platform Space and Time Raises $10M"</a>. CoinDesk.</cite>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <cite class="citation news cs1"><a rel="nofollow" class="external text" href="https://www.theblock.co/post/172780/microsofts-m12-leads-space-and-times-20-million-raise-to-bring-sql-to-web3">"Microsoft's M12 leads Space and Time's $20 million raise to bring SQL to Web3"</a>. The Block. 27 September 2022.</cite>

</li>

<li id="cite_note-34"><a href="#cite_ref-34">^</a> <cite id="CITEREFZhouDiroSainiKaisar2024" class="citation journal cs1">Zhou, Lu; Diro, Abebe; Saini, Akanksha; Kaisar, Shahriar; Hiep, Pham Cong (2024-02-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jisa.2023.103678">"Leveraging zero knowledge proofs for blockchain-based identity sharing: A survey of advancements, challenges and opportunities"</a>. Journal of Information Security and Applications. 80: 103678. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jisa.2023.103678">10.1016/j.jisa.2023.103678</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2214-2126">2214-2126</a>.</cite>

</li>

<li id="cite_note-35"><a href="#cite_ref-35">^</a> <cite id="CITEREFGoldreich1985" class="citation journal cs1">Goldreich, Oded (1985). "A zero-knowledge proof that a two-prime moduli is not a Blum integer". Unpublished Manuscript.</cite>

</li>

<li id="cite_note-36"><a href="#cite_ref-36">^</a> <cite id="CITEREFGoldreichMicaliWigderson1991" class="citation journal cs1">Goldreich, Oded; Micali, Silvio; Wigderson, Avi (1991). "Proofs that yield nothing but their validity". Journal of the ACM. 38 (3): 690–728. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.420.1478">10.1.1.420.1478</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F116825.116852">10.1145/116825.116852</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2389804">2389804</a>.</cite>

</li>

<li id="cite_note-37"><a href="#cite_ref-37">^</a> Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40–51

</li>

<li id="cite_note-38"><a href="#cite_ref-38">^</a> <cite id="CITEREFBen-OrGoldreichGoldwasserHastad1990" class="citation book cs1">Ben-Or, Michael; Goldreich, Oded; Goldwasser, Shafi; Hastad, Johan; Kilian, Joe; Micali, Silvio; Rogaway, Phillip (1990). "Everything provable is provable in zero-knowledge". In Goldwasser, S. (ed.). Advances in Cryptology – CRYPTO '88. Lecture Notes in Computer Science. Vol. 403. Springer-Verlag. pp. 37–56.</cite>

</li>

<li id="cite_note-39"><a href="#cite_ref-39">^</a> <cite id="CITEREFBen-OrGoldwasserKilianWidgerson1988" class="citation book cs1">Ben-Or, Michael; Goldwasser, Shafi; Kilian, Joe; Widgerson, Avi (1988). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/62212.62223">"Multi-prover interactive proofs: How to remove intractability"</a>. Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88. pp. 113–131. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F62212.62223">10.1145/62212.62223</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89791-264-0</bdi>.</cite>

</li>

<li id="cite_note-40"><a href="#cite_ref-40">^</a> <cite id="CITEREFDworkNaorSahai2004" class="citation journal cs1">Dwork, Cynthia; Naor, Moni; Sahai, Amit (2004). "Concurrent Zero Knowledge". Journal of the ACM. 51 (6): 851–898. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.716">10.1.1.43.716</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1039488.1039489">10.1145/1039488.1039489</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:52827731">52827731</a>.</cite>

</li>

<li id="cite_note-41"><a href="#cite_ref-41">^</a> <cite id="CITEREFFeigeShamir1990" class="citation book cs1">Feige, Uriel; Shamir, Adi (1990). "Witness indistinguishable and witness hiding protocols". Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90. pp. 416–426. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.73.3911">10.1.1.73.3911</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F100216.100272">10.1145/100216.100272</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0897913614</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11146395">11146395</a>.</cite>

</li>

<li id="cite_note-mouris21-42">^ <a href="#cite_ref-mouris21_42-0">a</a> <a href="#cite_ref-mouris21_42-1">b</a> <cite id="CITEREFMourisTsoutsos2021" class="citation journal cs1">Mouris, Dimitris; Tsoutsos, Nektarios Georgios (2021). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/9410618">"Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs"</a>. IEEE Transactions on Information Forensics and Security. 16: 3269–3284. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIFS.2021.3074869">10.1109/TIFS.2021.3074869</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1556-6021">1556-6021</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:222069813">222069813</a>.</cite>

</li>

<li id="cite_note-43"><a href="#cite_ref-43">^</a> <cite id="CITEREFParnoHowellGentryRaykova2013" class="citation book cs1">Parno, B.; Howell, J.; Gentry, C.; Raykova, M. (May 2013). "Pinocchio: Nearly Practical Verifiable Computation". 2013 IEEE Symposium on Security and Privacy. pp. 238–252. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSP.2013.47">10.1109/SP.2013.47</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7695-4977-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1155080">1155080</a>.</cite>

</li>

<li id="cite_note-44"><a href="#cite_ref-44">^</a> <cite id="CITEREFCostelloFournetHowellKohlweiss2015" class="citation book cs1">Costello, Craig; Fournet, Cedric; Howell, Jon; Kohlweiss, Markulf; Kreuter, Benjamin; Naehrig, Michael; Parno, Bryan; Zahur, Samee (May 2015). <a rel="nofollow" class="external text" href="https://www.research.ed.ac.uk/en/publications/37920e55-65aa-4a42-b678-ef5902a5dd45">"Geppetto: Versatile Verifiable Computation"</a>. 2015 IEEE Symposium on Security and Privacy. pp. 253–270. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSP.2015.23">10.1109/SP.2015.23</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/20.500.11820%2F37920e55-65aa-4a42-b678-ef5902a5dd45">20.500.11820/37920e55-65aa-4a42-b678-ef5902a5dd45</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4673-6949-7</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3343426">3343426</a>.</cite>

</li>

<li id="cite_note-45"><a href="#cite_ref-45">^</a> <cite id="CITEREFBen-SassonChiesaGenkinTromer2013" class="citation book cs1">Ben-Sasson, Eli; Chiesa, Alessandro; Genkin, Daniel; Tromer, Eran; Virza, Madars (2013). "SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge". Advances in Cryptology – CRYPTO 2013. Lecture Notes in Computer Science. Vol. 8043. pp. 90–108. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-40084-1_6">10.1007/978-3-642-40084-1_6</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F87953">1721.1/87953</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-40083-4</bdi>.</cite>

</li>

<li id="cite_note-46"><a href="#cite_ref-46">^</a> <cite id="CITEREFWahbySettyRenBlumberg2015" class="citation journal cs1">Wahby, Riad S.; Setty, Srinath; Ren, Zuocheng; Blumberg, Andrew J.; Walfish, Michael (2015). "Efficient RAM and Control Flow in Verifiable Outsourced Computation". Proceedings 2015 Network and Distributed System Security Symposium. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.14722%2Fndss.2015.23097">10.14722/ndss.2015.23097</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-891562-38-9</bdi>.</cite>

</li>

<li id="cite_note-47"><a href="#cite_ref-47">^</a> <cite id="CITEREFEberhardtTai2018" class="citation book cs1">Eberhardt, Jacob; Tai, Stefan (July 2018). "ZoKrates - Scalable Privacy-Preserving Off-Chain Computations". 2018 IEEE International Conference on Internet of Things (IThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). pp. 1084–1091. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FCybermatics_2018.2018.00199">10.1109/Cybermatics_2018.2018.00199</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-5386-7975-3</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:49473237">49473237</a>.</cite>

</li>

<li id="cite_note-48"><a href="#cite_ref-48">^</a> <cite id="CITEREFKosbaPapamanthouShi2018" class="citation book cs1">Kosba, Ahmed; Papamanthou, Charalampos; Shi, Elaine (May 2018). "XJsnark: A Framework for Efficient Verifiable Computation". 2018 IEEE Symposium on Security and Privacy (SP). pp. 944–961. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSP.2018.00018">10.1109/SP.2018.00018</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-5386-4353-2</bdi>.</cite>

</li>

<li id="cite_note-49"><a href="#cite_ref-49">^</a> <cite id="CITEREFZhangGenkinKatzPapadopoulos2018" class="citation book cs1">Zhang, Yupeng; Genkin, Daniel; Katz, Jonathan; Papadopoulos, Dimitrios; Papamanthou, Charalampos (May 2018). "VRAM: Faster Verifiable RAM with Program-Independent Preprocessing". 2018 IEEE Symposium on Security and Privacy (SP). pp. 908–925. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSP.2018.00013">10.1109/SP.2018.00013</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-5386-4353-2</bdi>.</cite>

</li>

<li id="cite_note-50"><a href="#cite_ref-50">^</a> <cite id="CITEREFBen-SassonChiesaTromerVirza2014" class="citation journal cs1">Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars (20 August 2014). <a rel="nofollow" class="external text" href="https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/ben-sasson">"Succinct non-interactive zero knowledge for a von Neumann architecture"</a>. Proceedings of the 23rd USENIX Conference on Security Symposium. USENIX Association: 781–796. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781931971157</bdi>.</cite>

</li>

<li id="cite_note-51"><a href="#cite_ref-51">^</a> <cite id="CITEREFKosbaPapadopoulosPapamanthouSong2020" class="citation journal cs1">Kosba, Ahmed; Papadopoulos, Dimitrios; Papamanthou, Charalampos; Song, Dawn (2020). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2020/278">"MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs"</a>. Cryptology ePrint Archive.</cite>

</li>

<li id="cite_note-52"><a href="#cite_ref-52">^</a> <cite id="CITEREFMallerBoweKohlweissMeiklejohn2019" class="citation book cs1">Maller, Mary; Bowe, Sean; Kohlweiss, Markulf; Meiklejohn, Sarah (6 November 2019). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3319535.3339817">"Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings"</a>. <a rel="nofollow" class="external text" href="https://www.research.ed.ac.uk/en/publications/739b94f1-54f0-4ec3-9644-3c95eea1e8f5">Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security</a>. Association for Computing Machinery. pp. 2111–2128. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3319535.3339817">10.1145/3319535.3339817</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/20.500.11820%2F739b94f1-54f0-4ec3-9644-3c95eea1e8f5">20.500.11820/739b94f1-54f0-4ec3-9644-3c95eea1e8f5</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781450367479</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:242772913">242772913</a>.</cite>

</li>

<li id="cite_note-53"><a href="#cite_ref-53">^</a> <cite id="CITEREFChiesaHuMallerMishra2020" class="citation book cs1">Chiesa, Alessandro; Hu, Yuncong; Maller, Mary; Mishra, Pratyush; Vesely, Noah; Ward, Nicholas (2020). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-030-45721-1_26">"Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS"</a>. Advances in Cryptology – EUROCRYPT 2020. Lecture Notes in Computer Science. Vol. 12105. Springer International Publishing. pp. 738–768. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-45721-1_26">10.1007/978-3-030-45721-1_26</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-45720-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:204772154">204772154</a>.</cite>

</li>

<li id="cite_note-54"><a href="#cite_ref-54">^</a> <cite id="CITEREFGabizonWilliamsonCiobotaru2019" class="citation journal cs1">Gabizon, Ariel; Williamson, Zachary J.; Ciobotaru, Oana (2019). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2019/953">"PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge"</a>. Cryptology ePrint Archive.</cite>

</li>

<li id="cite_note-55"><a href="#cite_ref-55">^</a> <cite id="CITEREFBünzFischSzepieniec2020" class="citation book cs1">Bünz, Benedikt; Fisch, Ben; Szepieniec, Alan (2020). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-030-45721-1_24">"Transparent SNARKs from DARK Compilers"</a>. Advances in Cryptology – EUROCRYPT 2020. Lecture Notes in Computer Science. Vol. 12105. Springer International Publishing. pp. 677–706. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-45721-1_24">10.1007/978-3-030-45721-1_24</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-45720-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:204892714">204892714</a>.</cite>

</li>

<li id="cite_note-56"><a href="#cite_ref-56">^</a> <cite id="CITEREFWahbyTziallaShelatThaler2018" class="citation book cs1">Wahby, Riad S.; Tzialla, Ioanna; Shelat, Abhi; Thaler, Justin; Walfish, Michael (May 2018). "Doubly-Efficient zkSNARKs Without Trusted Setup". 2018 IEEE Symposium on Security and Privacy (SP). pp. 926–943. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSP.2018.00060">10.1109/SP.2018.00060</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-5386-4353-2</bdi>.</cite>

</li>

<li id="cite_note-57"><a href="#cite_ref-57">^</a> <cite id="CITEREFBoweGriggHopwood2019" class="citation journal cs1">Bowe, Sean; Grigg, Jack; Hopwood, Daira (2019). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2019/1021">"Recursive Proof Composition without a Trusted Setup"</a>. Cryptology ePrint Archive.</cite>

</li>

<li id="cite_note-58"><a href="#cite_ref-58">^</a> <cite id="CITEREFZhangXieZhangSong2020" class="citation book cs1">Zhang, Jiaheng; Xie, Tiancheng; Zhang, Yupeng; Song, Dawn (May 2020). "Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof". 2020 IEEE Symposium on Security and Privacy (SP). pp. 859–876. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSP40000.2020.00052">10.1109/SP40000.2020.00052</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-7281-3497-0</bdi>.</cite>

</li>

<li id="cite_note-59"><a href="#cite_ref-59">^</a> <cite id="CITEREFAmesHazayIshaiVenkitasubramaniam2017" class="citation book cs1">Ames, Scott; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 October 2017). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/3133956.3134104">"Ligero"</a>. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery. pp. 2087–2104. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3133956.3134104">10.1145/3133956.3134104</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781450349468</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5348527">5348527</a>.</cite>

</li>

<li id="cite_note-60"><a href="#cite_ref-60">^</a> <cite id="CITEREFBen-SassonChiesaRiabzevSpooner2019" class="citation book cs1">Ben-Sasson, Eli; Chiesa, Alessandro; Riabzev, Michael; Spooner, Nicholas; Virza, Madars; Ward, Nicholas P. (2019). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007%2F978-3-030-17653-2_4">"Aurora: Transparent Succinct Arguments for R1CS"</a>. Advances in Cryptology – EUROCRYPT 2019. Lecture Notes in Computer Science. Vol. 11476. Springer International Publishing. pp. 103–128. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-17653-2_4">10.1007/978-3-030-17653-2_4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-17652-5</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:52832327">52832327</a>.</cite>

</li>

<li id="cite_note-61"><a href="#cite_ref-61">^</a> <cite id="CITEREFBen-SassonBentovHoreshRiabzev2019" class="citation book cs1">Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinon; Riabzev, Michael (2019). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-030-26954-8_23">"Scalable Zero Knowledge with No Trusted Setup"</a>. Advances in Cryptology – CRYPTO 2019. Lecture Notes in Computer Science. Vol. 11694. Springer International Publishing. pp. 701–732. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-26954-8_23">10.1007/978-3-030-26954-8_23</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-26953-1</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:199501907">199501907</a>.</cite>

</li>

<li id="cite_note-62"><a href="#cite_ref-62">^</a> <cite id="CITEREFChaliasosErnstbergerTheodoreWong2024" class="citation book cs1">Chaliasos, Stefanos; Ernstberger, Jens; Theodore, David; Wong, David; Jahanara, Mohammad; Livshits, Benjamin (2024). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.5555/3698900.3699116">"SoK: What Don't We Know? Understanding Security Vulnerabilities in SNARKs"</a>. SEC '24: Proceedings of the 33rd USENIX Conference on Security Symposium. pp. 3855–3872. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2402.15293">2402.15293</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-939133-44-1</bdi>.</cite>

</li>

<li id="cite_note-63"><a href="#cite_ref-63">^</a> <cite id="CITEREFPailoorChenWangRodríguez2023" class="citation journal cs1">Pailoor, Shankara; Chen, Yanju; Wang, Franklyn; Rodríguez, Clara; Van Geffen, Jacob; Morton, Jason; Chu, Michael; Gu, Brian; Feng, Yu; Dillig, Işıl (2023). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3591282">"Automated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs"</a>. Proceedings of the ACM on Programming Languages. 7: 1510–1532. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3591282">10.1145/3591282</a>.</cite>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-04" href="https://en.wikipedia.org/wiki/?title=Zero-knowledge_proof&oldid=1298731730">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>